The present invention generally relates to semiconductor memory devices and more specifically to detecting multiple matches between search and stored data in memory systems such as high-density Content Addressable Mermory (CAM).
In many conventional memory systems, such as random access memory, binary digits (bits) are stored in memory cells, and are accessed by a processor that specifies a linear address that is associated with the given cell. This system provides rapid access to any portion of the memory system within certain limitations. To facilitate processor control, each operation that accesses memory must declare, as a part of the instruction, the address of the memory cell/cells required. As the amount of memory increases the number of bits per instruction needed to reference a memory cell also increases. This diminishes the efficiency of the system. In addition to this drawback, standard memory systems are not well designed for a content based search. Content based searches in standard memory require a software based algorithmic search under the control of the microprocessor. These searches are neither quick nor efficient in using processor resources.
To overcome these inadequacies an associative memory system called Content Addressable Memory (CAM) has been developed. CAM allows cells to be referenced by their contents, so it first found use in lookup table implementations such as cache memory subsystems and is now rapidly finding use in networking systems. CAM""s most valuable feature is its ability to perform a search and compare as a single operation. Specified user data and stored data can be compared and match and mismatch results can be returned by allowing the contents of a comparand register to be compared directly with all addresses held in a given memory system""s address space simultaneously.
In addition to the rows and columns of memory cells, that are common to most memory systems, CAM also has a matchline and a matchline detection circuit (DTC). The DTC is a sense amplifier that senses the changes in the logic state of a matchline for the cells in that row. The DTC detects a match or a mismatch during a CAM search and compare operation. Though in many early applications it was not a concern, presently the detection of multiple matches on a matchline is of great interest. Distinguishing between a match and mismatch condition is as simple as declaring a threshold voltage or current level between the match and mismatch levels, and determining on which side of the threshold the matchline level was. This cannot be done with the presence of multiple matches, as the effect that it has is simply to increase the decay rate of the voltage or current level.
In a typical CAM system, various memory cells, arranged in a row, are connected by a matchline to a detection circuit (DTC). Running orthogonal to the matchlines are search lines that carry loaded search data to compare with stored data in the columns of CAM cells. Typically, matchlines are precharged to a matchline precharge voltage, for example, VDD. If a search result is a match, i.e. search data on the search line matches stored data in the CAM cell, then there is no change in the matchline voltage level, i.e. it remains at its precharge state, VDD. In the case of a mismatch, a direct current path is established between the respective matchline and VSS via the CAM cell and the voltage level on that matchline begins to decrease. This voltage drop is then detected by the respective DTC. Thus to detect a mismatch, each DTC, associated with each matchline, must detect whether a differing voltage level develops as a result of the search and compare operation. However, it is advantageous to determine whether a detected match has resulted from a single row or from multiple rows.
In order to detect multiple matches, otherwise referred to as hits, the problem encountered is one of detecting different voltage levels that can develop on a line. U.S. Pat. No. 5,012,448 to Matsuoka et al. describes a method for detecting a voltage level in a multilevel read only memory (ROM) cell. As shown in FIG. 1, the method and apparatus described therein use a pair of CMOS inverters that are operated as small signal amplifiers with an NMOS device used for current sensing. Both reference and active side sources are also fed into a current mirror. Though this design accomplishes the desired task of multilevel sensing, it does so at the cost of increased heat dissipation, and a limited output voltage swing. This increase in heat is a direct result of high power consumption by the discrete components and is a limiting factor in the attempt to shrink the component size so that it occupies less circuit area.
U.S. Pat. No. 5,446,686 to Bosnyak et al. describes a method and an apparatus for detecting multiple address matches in a CAM. The described apparatus, as shown in FIGS. 2a, 2b and 2c uses a pair of xe2x80x98hitxe2x80x99 and xe2x80x98dhitxe2x80x99 lines that are connected to the power supply terminal (VDD) through a pair of pull-up PMOS transistors. A set of NMOS devices N0-N3 on the xe2x80x98hitxe2x80x99 line operate in saturation since the voltages across the drain and source terminals are always above a threshold compared to the gate-to-source voltage (Vgs) of these devices. The reference transistor has a width to length ratio that is 1.5 times in dimension relative to any one of the NMOS devices N0-N3 to provide a 1.5 times saturation current. The reference transistor Nref also operates in its saturation region. The Vgs of the Nref device is generated using a rather complex reference circuit to ensure appropriate compensation for temperature and voltage characteristics. Furthermore, the described apparatus uses a comparator to compare the current difference generated on the xe2x80x98hitxe2x80x99 and xe2x80x98dhitxe2x80x99 lines for a single and multiple match generation. The comparator is a two-stage area-intensive component that uses bipolar transistors and resistors for achieving the desired output.
One limitation of this application is as follows. In order to operate the NMOS devices N0-N3 and Nref in saturation, the pull-up PMOS devices connecting the xe2x80x98hitxe2x80x99 and xe2x80x98dhitxe2x80x99 lines to the power supply terminal have to have relatively low resistivity such that the voltage drop is not significant across them while the devices N0-N3 and Nref turn on during sensing. This is required to ensure that the voltage across the drain-to-source channel does not change significantly. This is achieved at the cost of relatively high current consumption through the xe2x80x98hitxe2x80x99 and xe2x80x98dhitxe2x80x99 lines during the entire operation, which presents a limitation for multiple-match detection within high density CAMs.
Furthermore, to operate Nref in saturation, a relatively complex compensating reference circuit is required to ensure compensation for temperature and voltage fluctuations in order to develop a constant reference current. The comparator itself is area consuming and consumes constant current. The requirement of bipolar devices presents a limitation for use in dynamic random access memories (DRAM), which are entirely CMOS based.
In conclusion, the increased demand for large memory systems, and the desire to efficiently use these systems for more than simple sequential access makes it desirable to provide a multilevel sense detection method that in an ideal embodiment combines fast sensing with low power consumption.
It is an object of the present invention to provide a match detection method that obviates or mitigates at least one disadvantage of prior match detection methods. It is a particular object to provide a multilevel sense detection method that is both fast and consumes less power than previously known signal detection circuits.
In accordance with a first aspect of the present invention, there is provided a method for detecting n match conditions within a CAM array. The method consists of precharging a sense node and a reference node of a differential amplifier in an inactive state to a supply voltage level. The voltage level of the reference node is then changed to a reference voltage level in a predetermined voltage range by turning on a reference device. The voltage level of the sense node is then changed to a sensed voltage level dependent on a number of match condition signals by turning on a corresponding number of matchline devices coupled in parallel to the sense node, and the reference voltage level is compared to the sensed voltage level by switching the differential amplifier to an active state. An output signal corresponding to the result of the comparison is then provided from the differential amplifier. The method can further include a step of switching the differential amplifier to the inactive state when the output signal is provided, and latching the output signal.
In a presently preferred embodiment of the method of the present invention, the reference node voltage level and the sense node voltage level start changing from the supply voltage level at about the same time. The differential amplifier is switched to the active state at a predetermined time delay after the reference node voltage level and the sense node voltage level start changing.
In yet another preferred embodiment of the method of the present invention, the predetermined voltage range is between a voltage level corresponding to n match condition signals and nxe2x88x921 match condition signals.